perm filename V236.XGP[TEX,DEK] blob sn#521448 filedate 1980-07-10 generic text, type T, neo UTF8
/NOWRAPAROUND/LMAR=50/TMAR=50/RMAR=1700/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=000000057*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β	[␈↓ α4␈ε"SECTION␈α3.6␈αof␈αTHE␈αAR␈α⎇T␈αOF␈αCOMPUTER␈αPR␈α␈OGRAMMING
␈β
ε␈↓ β'␈ε6⎇␈ε"␈α1980␈αAddison↑W␈α⎇esley␈αPublishing␈αCompan␈α␈y,␈αInc.
␈β⊃H␈↓ ε2␈ε$0
␈β∪(

␈β↓U␈↓ ↓H␈ε"170␈↓ 
}␈ε"3.6
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα$␈↓ ↓H␈ε=3␈α␈.6.␈α∩SUM␈α␈MARY
␈βαi␈↓ ↓H␈ε"W␈↓ ∧7␈ε"a␈α∂fairly␈α⊂large␈α∂n␈α␈um␈α␈ber␈α∂of␈α∂topics␈↓ λ4␈ε"in␈α∂this␈α∂chapter:␈α∪h␈α↓o␈α␈w␈α∂to
␈βαn␈↓ ↓l␈ε.E␈α∂HA␈α|VE␈α∂CO␈α␈V␈α↓ER␈α␈ED
␈ββ∃␈↓ ↓H␈ε"generate␈αλrandom␈αλn␈α␈um␈α␈bers,␈α	h␈α↓o␈α␈w␈αλto␈α	test␈αλthem,␈α	h␈α↓o␈α␈w␈αλto␈α	m␈α↓odify␈αλthem␈αλin␈αλapplications,
␈ββ@␈↓ ↓H␈ε"and␈α
h␈α↓o␈α␈w␈α∞to␈α∞deriv␈α␈e␈α
theoretical␈α∞facts␈α
about␈α∞them.␈α∃Perhaps␈α∞the␈α
main␈α∞question␈α
in
␈ββk␈↓ ↓H␈ε"man␈α␈y␈α
readers'␈α∞minds␈α
will␈α∞be,␈α
\What␈α∞is␈α
the␈α∞result␈α
of␈α∞all␈α
this␈α∞theory?␈α∀What␈α∞is␈α
a
␈β∧⊗␈↓ ↓H␈ε"simple,␈α
virtuous␈αgenerator␈α
I␈α
can␈α
use␈αin␈α
m␈α␈y␈α
programs␈α
in␈αorder␈α
to␈α
ha␈α␈v␈α␈e␈α
a␈αreliable
␈β∧A␈↓ ↓H␈ε"source␈αof␈αrandom␈αn␈α␈um␈α␈bers?"
␈β∧n␈↓ α␈ε"The␈αdetailed␈αin␈α␈v␈α␈estigations␈αin␈αthis␈αchapter␈αsuggest␈αthat␈αthe␈αfollo␈α␈wing␈αproce-
␈β¬→␈↓ ↓H␈ε"dure␈α	giv␈α␈es␈α	the␈α	\nicest"␈α	and␈α	\simplest"␈α	random␈α	n␈α␈um␈α␈ber␈αλgenerator␈α	for␈α	the␈α	machine
␈β¬D␈↓ ↓H␈ε"language␈α∂of␈α∂m␈α↓ost␈α∂computers:␈↓ ¬(␈ε"A␈α␈t␈α∂the␈α∂beginning␈α∂of␈α∂the␈α∂program,␈α∂set␈α∂an␈α∂in␈α␈teger
␈β¬o␈↓ ↓H␈ε"v␈α}ariable␈↓ αM␈ε(X␈↓ αz␈ε"to␈αsome␈α
v␈α}alue␈↓ ∧Y␈ε(X␈↓ ¬λ␈ε".␈α∂This␈αv␈α}ariable␈↓ εx␈ε(X␈↓ π%␈ε"is␈α
to␈αbe␈αused␈α
only␈αfor␈αthe␈α
purpose
␈β¬|␈↓ ∧w␈ε%0
␈βε≠␈↓ ↓H␈ε"of␈αrandom␈α
n␈α␈um␈α␈ber␈α
generation.␈α∩Whenev␈α␈er␈α
a␈α
new␈αrandom␈α
n␈α␈um␈α␈ber␈α
is␈α
required␈αby
␈βεF␈↓ ↓H␈ε"the␈αprogram,␈αset
␈βεt␈↓ ¬
␈ε(X␈↓ ¬9␈ε6␈ ␈ε"␈α
(␈ε(a␈↓ εε␈ε(X␈↓ ε0␈ε"+␈ε(␈αλc␈ε")␈↓ ε⎇␈ε"mod␈↓ πG␈ε(m␈↓ α␈ε"(1)
␈βπ<␈↓ ↓H␈ε"and␈αuse␈α
the␈αnew␈α
v␈α}alue␈αof␈↓ ∧↑␈ε(X␈↓ ¬␈ε"as␈α
the␈αrandom␈α
v␈α}alue.␈α⊃It␈α
is␈αnecessary␈α
to␈αch␈α↓o␈α↓ose␈↓ 
t␈ε(X␈↓ "␈ε",
␈βπI␈↓ ∩␈ε%0
␈βπg␈↓ ↓H␈ε(a␈ε",␈ε(␈α
c␈ε"␈α↓,␈α
and␈ε(␈α∞m␈ε"␈α
properly,␈α∞and␈α
to␈α
use␈α∞the␈α
random␈α∞n␈α␈um␈α␈bers␈α
wisely,␈α∞according␈α
to␈α
the
␈βλ∪␈↓ ↓H␈ε"follo␈α␈wing␈αprinciples:
␈βλ[␈↓ ↓j␈ε"i)␈↓ α␈ε"The␈α∂\␈↓ αk␈ε"seed"␈α⊂n␈α␈um␈α␈ber␈↓ ∧T␈ε(X␈↓ ¬∩␈ε"ma␈α␈y␈α∂be␈α∂ch␈α↓osen␈α⊂arbitrarily.␈α→If␈α⊂the␈α∂program␈α∂is␈α∂run
␈βλh␈↓ ∧r␈ε%0
␈β	π␈↓ α␈ε"sev␈α␈eral␈α
times␈αand␈α
a␈αdi{eren␈α␈t␈α
source␈αof␈α
random␈αn␈α␈um␈α␈bers␈α
is␈αdesired␈α
each␈α
time,
␈β	2␈↓ α␈ε"set␈↓ αG␈ε(X␈↓ β¬␈ε"to␈α∞the␈α∂last␈α∂v␈α}alue␈α∂attained␈α∂by␈↓ εb␈ε(X␈↓ π∪␈ε"on␈α∂the␈α∞preceding␈α∂run;␈α⊃or␈α∂(if␈α∞m␈α↓ore
␈β	>␈↓ αe␈ε%0
␈β	]␈↓ α␈ε"con␈α␈v␈α␈enien␈α␈t)␈α
set␈↓ ∧β␈ε(X␈↓ ∧?␈ε"to␈α
the␈αcurren␈α␈t␈α
date␈α
and␈αtime.␈α∪If␈↓ λF␈ε"the␈α
program␈α
ma␈α␈y␈αneed
␈β	i␈↓ ∧!␈ε%0
␈β
λ␈↓ α␈ε"to␈αbe␈αrerun␈αlater␈αwith␈αthe␈ε/␈αsame␈ε"␈αrandom␈αn␈α␈um␈α␈bers␈α(e.g.,␈αwhen␈αdebugging),␈αbe
␈β
3␈↓ α␈ε"sure␈αto␈αprin␈α␈t␈αout␈↓ ∧≥␈ε(X␈↓ ∧X␈ε"if␈αit␈αisn't␈αotherwise␈αkn␈α↓o␈α␈wn.
␈β
@␈↓ ∧;␈ε%0
␈β
h␈↓ πx␈ε%30
␈β
n␈↓ ↓`␈ε"ii)␈↓ α␈ε"The␈α∂n␈α␈um␈α␈ber␈ε(␈α⊂m␈ε"␈α∂sh␈α↓ould␈α∂be␈α∂large,␈α⊃sa␈α␈y␈α∂at␈α∂least␈↓ πf␈ε"2␈↓ λ_␈ε".␈α→It␈α⊂ma␈α␈y␈α∂con␈α␈v␈α␈enien␈α␈tly␈α∂be
␈β→␈↓ α␈ε"tak␈α␈en␈α⊃as␈α∩the␈α⊃computer's␈α⊃w␈α␈ord␈α⊃size,␈α∪since␈α⊃this␈α∩mak␈α␈es␈α⊃the␈α⊃computation␈α⊃of
␈βD␈↓ α␈ε"(␈ε(a␈↓ α+␈ε(X␈↓ αU␈ε"+␈ε(␈αλc␈ε"␈α↓)␈↓ β#␈ε"mod␈↓ βm␈ε(m␈ε"␈αquite␈α
e}cien␈α␈t.␈α⊂Section␈α3.2.1.1␈α
discusses␈αthe␈αch␈α↓oice␈αof␈ε(␈αm␈ε"␈αin
␈βp␈↓ α␈ε"m␈α↓ore␈α∂detail.␈α~The␈α∂computation␈α∂of␈α∂(␈ε(a␈↓ εT␈ε(X␈↓ π↓␈ε"+␈ε(␈α
c␈ε")␈↓ πP␈ε"mod␈↓ λ~␈ε(m␈ε"␈α∂m␈α␈ust␈α∂be␈α∂done␈ε/␈α∂exactly␈ε",
␈β≠␈↓ α␈ε"with␈αn␈α↓o␈αroundo{␈αerror.
␈βU␈↓ ↓V␈ε"iii)␈↓ α␈ε"If␈ε(␈αm␈ε"␈αis␈αa␈αpo␈α␈w␈α␈er␈αof␈α2␈α(i.e.,␈αif␈αa␈αbinary␈αcomputer␈αis␈αbeing␈αused),␈αpick␈ε(␈αa␈ε"␈αso␈αthat
␈β
␈↓ α␈ε(a␈↓ α%␈ε"mod␈↓ αo␈ε"8␈α
=␈α
5.␈α∂If␈ε(␈α
m␈ε"␈α	is␈α
a␈α
po␈α␈w␈α␈er␈α
of␈α	10␈α
(i.e.,␈α
if␈α
a␈α
decimal␈α	computer␈α
is␈α
being␈α	used),
␈β
,␈↓ α␈ε"ch␈α↓o␈α↓ose␈ε(␈αa␈ε"␈αso␈αthat␈ε(␈αa␈↓ ∧1␈ε"mod␈↓ ∧{␈ε"200␈α
=␈α
21.␈α⊂This␈αch␈α↓oice␈αof␈ε(␈αa␈ε"␈αtogether␈αwith␈αthe␈αch␈α↓oice
␈β
W␈↓ α␈ε"of␈ε(␈α⊂c␈ε"␈α⊂giv␈α␈en␈α∂belo␈α␈w␈α⊂ensures␈α⊂that␈α∂the␈α⊂random␈α∂n␈α␈um␈α␈ber␈α⊂generator␈α⊂will␈α∂produce
␈β∞α␈↓ α␈ε"all␈ε(␈α∂m␈ε"␈α∂di{eren␈α␈t␈α∂possible␈α∂v␈α}alues␈α∂of␈↓ ε$␈ε(X␈↓ εU␈ε"before␈α∂it␈α∂starts␈α∂to␈α∞repeat␈α∂(see␈α∂Section
␈β∞-␈↓ α␈ε"3.2.1.2)␈αand␈αensures␈αhigh␈α\potency"␈α(see␈αSection␈α3.2.1.3).
␈β∞h␈↓ ↓W␈ε"iv)␈↓ α␈ε"The␈α
m␈α␈ultiplier␈ε(␈αa␈ε"␈α
sh␈α↓ould␈α
preferably␈α
be␈αch␈α↓osen␈α
bet␈α␈w␈α␈een␈α
.01␈ε(m␈ε"␈αand␈α
.99␈ε(m␈ε",␈αand
␈β∂∪␈↓ α␈ε"its␈α∞binary␈α∞or␈α
decimal␈↓ ∧f␈ε"digits␈α∞sh␈α↓ould␈ε/␈α∞n␈α↓ot␈ε"␈α∞ha␈α␈v␈α␈e␈α
a␈α∞simple,␈α∞regular␈α∞pattern.␈α∃By
␈β∂ ␈↓ 	9␈ε↓␈
␈β∂>␈↓ α␈ε"ch␈α↓o␈α↓osing␈α⊃some␈α⊃haphazard␈α∩constan␈α␈t␈α⊃lik␈α␈e␈ε(␈α⊃a␈ε"␈α∩=␈α∪3141592621␈↓ 	G␈ε"which␈α⊃satis|es
␈β∂K␈↓ ¬M␈ε↓↓
␈β∂i␈↓ α␈ε"both␈αof␈α
the␈αconditions␈αin␈α
(iii)␈↓ ¬[␈ε",␈αone␈αalm␈α↓ost␈αalw␈α␈a␈α␈ys␈α
obtains␈αa␈αreasonably␈α
go␈α↓od
␈β⊂∃␈↓ α␈ε"m␈α␈ultiplier.␈α∩F␈α⎇urther␈α
testing␈α
sh␈α↓ould␈αof␈α
course␈α
be␈α
done␈αif␈α
the␈α
random␈αn␈α␈um␈α␈ber
␈β⊂@␈↓ α␈ε"generator␈α∞is␈α∂to␈α∞be␈α∞used␈α∂extensiv␈α␈ely;␈α∂for␈α∞example,␈α∂there␈α∂sh␈α↓ould␈α∞be␈α∞n␈α↓o␈α∞large
␈β⊂k␈↓ α␈ε"quotien␈α␈ts␈α∞when␈α∞Euclid's␈α∞algorithm␈α∞is␈α∞used␈α∞to␈α∞|nd␈α∞the␈α∞gcd␈α∂of␈ε(␈α∞a␈ε"␈α∞and␈ε(␈α∞m␈ε"␈α
(see
␈β⊃⊗␈↓ α␈ε"Section␈α∞3.3.3).␈α⊗The␈α∞m␈α␈ultiplier␈α∞sh␈α↓ould␈α∞pass␈α∞the␈α∞spectral␈α∞test␈α∞(Section␈α∞3.3.4)
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.6␈↓ 
v␈ε"171
␈β↓\␈↓ 	∪␈ε∞S␈α␈U␈α↓MMAR␈α}Y
␈βα$␈↓ α␈ε"and␈α
sev␈α␈eral␈α	tests␈α
of␈α	Section␈α
3.3.2,␈α
before␈α	it␈α
is␈α
considered␈α	to␈α
ha␈α␈v␈α␈e␈α	a␈α
truly␈α	clean
␈βαO␈↓ α␈ε"bill␈αof␈αhealth.
␈ββ¬␈↓ ↓a␈ε"v)␈↓ α␈ε"The␈αv␈α}alue␈α
of␈ε(␈αc␈ε"␈αis␈αimmaterial␈αwhen␈ε(␈α
a␈↓ εE␈ε"is␈αa␈α
go␈α↓od␈αm␈α␈ultiplier,␈αexcept␈αthat␈ε(␈α
c␈ε"␈αm␈α␈ust
␈ββ0␈↓ α␈ε"ha␈α␈v␈α␈e␈αn␈α↓o␈αfactor␈αin␈αcomm␈α↓on␈αwith␈ε(␈αm␈ε".␈α⊂Th␈α␈us␈αw␈α␈e␈αma␈α␈y␈αch␈α↓o␈α↓ose␈ε(␈αc␈ε"␈α
=␈α
1␈αor␈ε(␈αc␈ε"␈α
=␈ε(␈α
a␈ε".
␈ββf␈↓ ↓W␈ε"vi)␈↓ α␈ε"The␈αleast␈α
signi|can␈α␈t␈α(righ␈α␈t-hand)␈αdigits␈α
of␈↓ π,␈ε(X␈↓ π[␈ε"are␈αn␈α↓ot␈αv␈α␈ery␈α
random,␈αso␈αdeci-
␈β∧⊃␈↓ α␈ε"sions␈αbased␈αon␈α
the␈αn␈α␈um␈α␈ber␈↓ ¬;␈ε(X␈↓ ¬i␈ε"sh␈α↓ould␈αalw␈α␈a␈α␈ys␈α
be␈αin⎇uenced␈αprimarily␈αby␈αthe
␈β∧=␈↓ α␈ε"m␈α↓ost␈αsigni|can␈α␈t␈αdigits.␈α⊃It␈αis␈α
generally␈αbest␈αto␈αthink␈αof␈↓ λh␈ε(X␈↓ 	⊗␈ε"as␈αa␈αrandom␈αfrac-
␈β∧h␈↓ α␈ε"tion␈↓ αW␈ε(X␈↓ αy␈ε"/␈ε(m␈ε"␈αbet␈α␈w␈α␈een␈α0␈α
and␈α
1,␈αthat␈α
is,␈α
to␈αvisualize␈↓ λ␈ε(X␈↓ λ9␈ε"with␈α
a␈αdecimal␈α
poin␈α␈t␈αat
␈β¬∪␈↓ α␈ε"its␈αle$,␈αrather␈αthan␈αto␈αregard␈↓ ¬a␈ε(X␈↓ ε∂␈ε"as␈αa␈αrandom␈αin␈α␈teger␈αbet␈α␈w␈α␈een␈α0␈αand␈ε(␈αm␈ε6␈αε␈␈ε"␈απ1.
␈β¬>␈↓ α␈ε"T␈α⎇o␈αcompute␈αa␈αrandom␈αin␈α␈teger␈αbet␈α␈w␈α␈een␈α0␈αand␈↓ πU␈ε(k␈↓ πp␈ε6␈␈ε"␈απ1,␈αone␈αsh␈α↓ould␈αm␈α␈ultiply␈αby
␈β¬i␈↓ α␈ε(k␈↓ α,␈ε"and␈αtruncate␈αthe␈αresult␈α(see␈αthe␈αbeginning␈αof␈αSection␈α3.4.2).
␈βε∨␈↓ ↓M␈ε"vii)␈↓ α␈ε"An␈α∞importan␈α␈t␈α
limitation␈α∞on␈α
the␈α∞randomness␈α∞of␈α
sequence␈α∞(1)␈α
is␈α∞discussed␈α
in
␈βεJ␈↓ α␈ε"Section␈α⊂3.3.4,␈α⊂where␈α⊂it␈α∂is␈α⊂sh␈α↓o␈α␈wn␈α⊂that␈α∂the␈α⊂\␈↓ πD␈ε"accuracy"␈α∂in␈ε(␈α⊂t␈ε"␈α⊂dimensions␈α∂will
␈βεt␈↓ ¬5␈ε6p
␈βεv␈↓ α␈ε"be␈α∞only␈α∞about␈α
one␈α∞part␈α∞in␈↓ ¬S␈ε(m␈↓ ¬s␈ε".␈α∃Mon␈α␈te␈α∞Carlo␈α∞applications␈α∞requiring␈α
higher
␈βεw␈↓ ¬S␈∧εw¬Sα 
␈βεx␈↓ ¬@␈ε-t
␈βπ!␈↓ α␈ε"resolution␈α∞can␈α∞impro␈α␈v␈α␈e␈α
the␈α∞randomness␈α∞by␈α∞emplo␈α␈ying␈α∞techniques␈α
discussed
␈βπL␈↓ α␈ε"in␈αSection␈α3.2.2.
␈βλ␈↓ α␈ε"The␈αλabo␈α␈v␈α␈e␈αλcommen␈α␈ts␈αλapply␈αλprimarily␈αλto␈αλmachine-language␈αλcoding.␈α∂In␈αλhigher-
␈βλ8␈↓ ↓H␈ε"lev␈α␈el␈αλprogramming␈αλlanguages,␈α	w␈α␈e␈αλare␈αλo$en␈α	unable␈αλto␈αλuse␈αλsuch␈αλmachine-dependen␈α␈t
␈βλc␈↓ ↓H␈ε"features␈αλas␈αλin␈α␈teger␈αλarithmetic␈αλm␈α↓odulo␈αλthe␈αλw␈α␈ord␈αλsize,␈αλand␈αλcareful␈αλcompilers␈αλwill␈αλn␈α↓ot
␈β	∞␈↓ ↓H␈ε"allo␈α␈w␈αλus␈α	to␈α	compute␈α	the␈α	product␈α	of␈αλt␈α␈w␈α␈o␈α	large␈α	in␈α␈tegers.␈α∂An␈α↓other␈α	technique␈α	that␈αλw␈α␈e
␈β	9␈↓ ↓H␈ε"migh␈α␈t␈α
call␈α∞the␈↓ β4␈ε/subtractiv␈α␈e␈α∞meth␈α↓od␈ε"␈α
(exercise␈α∞3.2.2↑23)␈α∞can␈α∞be␈α
used␈α∞to␈α∞pro␈α␈vide␈α
a
␈β	d␈↓ ↓H␈ε"\portable"␈α	random␈α	n␈α␈um␈α␈ber␈α	generator␈↓ ε∀␈ε"that␈α	is␈α	e}cien␈α␈tly␈α	describable␈α	in␈α	an␈α␈y␈α	higher-
␈β
⊂␈↓ ↓H␈ε"lev␈α␈el␈α∞programming␈α∂language,␈α⊂since␈α∂it␈α∞mak␈α␈es␈α∂use␈α∂only␈α∂of␈α∂in␈α␈teger␈α∂arithmetic␈α∞be-
␈β
5␈↓ αv␈ε%9␈↓ ∧"␈ε%9
␈β
;␈↓ ↓H␈ε"t␈α␈w␈α␈een␈ε6␈α␈␈ε"1␈↓ αd␈ε"0␈↓ β∪␈ε"and␈α
+1␈↓ ∧⊂␈ε"0␈↓ ∧3␈ε".␈α⊃Here␈α
is␈αh␈α↓o␈α␈w␈α
the␈αsubtractiv␈α␈e␈α
meth␈α↓od␈αmigh␈α␈t␈αbe␈α
coded␈αin
␈β
f␈↓ αr␈ε",␈α∩as␈α⊃a␈α∩subroutine␈α∩that␈α∩deliv␈α␈ers␈α∩an␈α⊃arra␈α␈y␈α∩of␈α∩55␈α∩random␈α∩in␈α␈tegers␈α⊃at
␈β
h␈↓ ↓H␈ε#F␈α␈OR␈α⎇TRAN
␈β⊃␈↓ ↓H␈ε"once:
␈βf␈↓ α9␈ε5FUNCTI␈α␈ON␈α∪IRN55(I␈α␈A)
␈β∂␈↓ α9␈ε5DIMENS␈α␈ION␈α∪IA(1)
␈β8␈↓ ↓H␈ε5C␈↓ α9ASSUMI␈α␈NG␈α∪THAT␈α∪IA␈α␈(1),␈α∪...,␈α∩IA(55)␈α∪HAV␈α␈E␈α∪BEEN␈α∪SET␈α∩UP␈α∪PROPER␈α␈LY,
␈βa␈↓ ↓H␈ε5C␈↓ α9THIS␈α∪S␈α␈UBROUTINE␈α∩RESETS␈α∪THE␈α∩IA␈α∪ARRAY␈α∩TO␈α∪THE␈α∪NEX␈α␈T␈α∪55␈α∪NUMBE␈α␈RS
␈β
	␈↓ ↓H␈ε5C␈↓ α9OF␈α∪A␈α∪P␈α␈SEUDO-RAND␈α␈OM␈α∪SEQUENC␈α␈E,␈α∪AND␈α∪RET␈α␈URNS␈α∪THE␈α∪V␈α␈ALUE␈α∪1.
␈β
2␈↓ α9␈ε5DO␈α∪1␈α∪I␈α∩=␈α∪1,␈α∪24
␈β
[␈↓ α←␈ε5J␈α∪=␈α∩IA(I)␈α∪-␈α∪IA␈α␈(I+31)
␈β∞β␈↓ α←␈ε5IF␈α∪(␈α␈J␈α∪.LT.␈α∪0)␈α%J␈α∪=␈α∪J␈α∪+␈α∪1␈α␈000000000
␈β∞,␈↓ α←␈ε5IA(I␈α␈)␈α∪=␈α∪J
␈β∞U␈↓ ↓m␈ε51␈α9CONTIN␈α␈UE
␈β∞⎇␈↓ α9␈ε5DO␈α∪2␈α∪I␈α∩=␈α∪25,␈α∪55
␈β∂&␈↓ α←␈ε5J␈α∪=␈α∩IA(I)␈α∪-␈α∪IA␈α␈(I-24)
␈β∂O␈↓ α←␈ε5IF␈α∪(␈α␈J␈α∪.LT.␈α∪0)␈α%J␈α∪=␈α∪J␈α∪+␈α∪1␈α␈000000000
␈β∂w␈↓ α←␈ε5IA(I␈α␈)␈α∪=␈α∪J
␈β⊂ ␈↓ ↓m␈ε52␈α9CONTIN␈α␈UE
␈β⊂I␈↓ α9␈ε5IRN55=␈α␈1
␈β⊂q␈↓ α9␈ε5RETURN
␈β⊃~␈↓ α9␈ε5END
␈β∪(

␈β↓U␈↓ ↓H␈ε"172␈↓ 
}␈ε"3.6
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα$␈↓ ↓H␈ε"T␈α⎇o␈α
use␈α
these␈αn␈α␈um␈α␈bers␈α
in␈α
a␈↓ ε→␈ε"program,␈αlet␈↓ λM␈ε"be␈αan␈α
auxiliary␈α
in␈α␈teger
␈βα&␈↓ ∧e␈ε#F␈α␈OR␈α⎇TRAN␈↓ πd␈ε5JRAND
␈βαO␈↓ ↓H␈ε"v␈α}ariable;␈α⊃w␈α␈e␈α⊂ma␈α␈y␈α⊂obtain␈α⊂the␈α⊂next␈α⊂random␈α∂n␈α␈um␈α␈ber␈↓ λ%␈ε"(as␈α⊂a␈α⊂fraction␈α⊂bet␈α␈w␈α␈een␈α∂0
␈βαQ␈↓ λα␈ε5U
␈βαz␈↓ ↓H␈ε"and␈α1)␈αby␈αwriting␈αthe␈αfollo␈α␈wing␈αthree␈αstatemen␈α␈ts:
␈ββL␈↓ α9␈ε5JRAND␈α∩=␈α∪JRAND␈α∪+␈α∩1
␈ββw␈↓ α9␈ε5IF␈α∪(JR␈α␈AND␈α∪.GT.␈α∪5␈α␈5)␈α&JRAND␈α∩=␈α∪IRN55(IA␈α␈)
␈β∧"␈↓ α9␈ε5U␈α∪=␈α∪FL␈α␈OAT(IA(JRA␈α␈ND))␈α∪*␈α∪1.0␈α␈E-9
␈β∧p␈↓ ↓H␈ε"A␈α␈t␈α⊂the␈α⊂beginning␈α⊂of␈α⊂our␈α⊂program␈α⊂w␈α␈e␈α⊂need␈α⊂to␈α⊂write␈α⊂\␈↓ 
P␈ε""␈α⊂and
␈β∧r␈↓ λ"␈ε5DIMENS␈α␈ION␈α∪IA(55)
␈β¬≠␈↓ ↓H␈ε"\␈↓ αq␈ε""␈αand␈αw␈α␈e␈α
m␈α␈ust␈αalso␈αinitialize␈α
the␈↓ π/␈ε"arra␈α␈y.␈α⊃Appropriate␈αinitialization
␈β¬≥␈↓ ↓Z␈ε5JR␈α␈AND=55␈↓ ε⎇␈ε5IA
␈β¬F␈↓ ↓H␈ε"can␈αbe␈αdone␈αby␈αcalling␈αthe␈αfollo␈α␈wing␈αsubroutine␈αwith␈↓ λ>␈ε"set␈αto␈αan␈α␈y␈αin␈α␈teger␈αv␈α}alue
␈β¬H␈↓ λ␈ε5IX
␈β¬q␈↓ ↓H␈ε"(selected␈αlik␈α␈e␈↓ β≥␈ε(X␈↓ βW␈ε"in␈αrule␈α(i)␈αabo␈α␈v␈α␈e,␈αpreferably␈α
large):
␈β¬}␈↓ β;␈ε%0
␈βε@␈↓ α9␈ε5SUBROU␈α␈TINE␈α∪IN55(␈α␈IA,IX)
␈βεi␈↓ α9␈ε5DIMENS␈α␈ION␈α∪IA(1)
␈βπ⊃␈↓ ↓H␈ε5C␈↓ α9THIS␈α∪S␈α␈UBROUTINE␈α∩SETS␈α∪IA(1)␈α␈,␈α∪...,␈α∪IA(␈α␈55)␈α∪TO␈α∪STA␈α␈RTING
␈βπ:␈↓ ↓H␈ε5C␈↓ α9VALUES␈α∩SUITABLE␈α∩FOR␈α∪LATER␈α∩CALLS␈α∪ON␈α∪I␈α␈RN55(IA).
␈βπc␈↓ ↓H␈ε5C␈↓ α9IX␈α∪IS␈α∩AN␈α∪INTEGER␈α∩"SEED"␈α∪VA␈α␈LUE␈α∪BETWEE␈α␈N␈α∪0␈α∪AND␈α∪99␈α␈9999999.
␈βλ␈↓ α9␈ε5IA(55)␈α∩=␈α∪IX
␈βλ4␈↓ α9␈ε5J␈α∪=␈α∪IX
␈βλ]␈↓ α9␈ε5K␈α∪=␈α∪1
␈β	ε␈↓ α9␈ε5DO␈α∪1␈α∪I␈α∩=␈α∪1,␈α∪54
␈β	.␈↓ α←␈ε5II␈α∪=␈α∩MOD(21*I,␈α∩55)
␈β	W␈↓ α←␈ε5IA(I␈α␈I)␈α∪=␈α∪K
␈β
␈↓ α←␈ε5K␈α∪=␈α∩J␈α∪-␈α∪K
␈β
(␈↓ α←␈ε5IF␈α∪(␈α␈K␈α∪.LT.␈α∪0)␈α%K␈α∪=␈α∪K␈α∪+␈α∪1␈α␈000000000
␈β
Q␈↓ α←␈ε5J␈α∪=␈α∩IA(II)
␈β
z␈↓ ↓m␈ε51␈α9CONTIN␈α␈UE
␈β"␈↓ ↓H␈ε5C␈↓ α9THE␈α∪NE␈α␈XT␈α∪THREE␈α∪L␈α␈INES␈α∪"WARM␈α∩UP"␈α∪THE␈α∪G␈α␈ENERATOR.
␈βK␈↓ α9␈ε5IRN55(␈α␈IA)
␈βt␈↓ α9␈ε5IRN55(␈α␈IA)
␈β≤␈↓ α9␈ε5IRN55(␈α␈IA)
␈βE␈↓ α9␈ε5RETURN
␈βn␈↓ α9␈ε5END
␈β
≤␈↓ ↓H␈ε↓␈
␈β
;␈↓ ↓V␈ε"This␈α∞subroutine␈α∂computes␈α∞a␈↓ ¬!␈ε"Fibonacci-lik␈α␈e␈α∂sequence;␈α⊂m␈α␈ultiplication␈α∞of␈α∞indices
␈β
f␈↓ ↓H␈ε"by␈αλ21␈α	spreads␈αλthe␈α	v␈α}alues␈αλaround␈α	so␈α	as␈αλto␈α	alleviate␈αλinitial␈α	n␈α↓onrandomness␈αλproblems
␈β∞␈↓ π)␈ε%29␈↓ λ,␈ε%9␈↓ 	
␈ε%3␈α↓0
␈β∞⊃␈↓ ↓H␈ε"such␈α∞as␈α∞th␈α↓ose␈α∞in␈α∞exercise␈α∞3.2.2↑2.␈α⊗Note␈α∞that␈↓ π↔␈ε"2␈↓ πV␈ε"<␈α∞1␈↓ λ~␈ε"0␈↓ λJ␈ε"<␈↓ λ{␈ε"2␈↓ 	-␈ε";␈α∂an␈α␈y␈α∞large␈α∞ev␈α␈en
␈β∞7␈↓ εb␈ε%9
␈β∞=␈↓ ↓H␈ε"n␈α␈um␈α␈ber␈αma␈α␈y␈α
actually␈αbe␈αsubstituted␈αfor␈α1␈↓ εP␈ε"0␈↓ ε}␈ε"in␈αthese␈αroutines,␈αif␈αa␈α
corresponding
␈β∞h␈↓ ↓H␈ε"change␈α∞is␈α∂made␈α∂in␈α∞the␈α∂computation␈α∂of␈α∂the␈α∞random␈α∂fraction␈↓ 	≡␈ε".␈α_F␈α⎇urtherm␈α↓ore␈α∞it
␈β∞j␈↓ 	␈ε5U
␈β∂∪␈↓ ↓H␈ε"w␈α␈ould␈α	be␈α	possible␈α	to␈α	w␈α␈ork␈α	directly␈α
with␈↓ ε-␈ε"⎇oating␈α	poin␈α␈t␈α	n␈α␈um␈α␈bers␈α	instead␈α	of␈α	in␈α␈tegers
␈β∂>␈↓ ↓H␈ε"by␈α
making␈α
appropriate␈α
changes␈α
to␈α
these␈α
programs,␈ε/␈αpro␈α␈vided␈ε"␈α
that␈α
the␈α
computer's
␈β∂i␈↓ ↓H␈ε"⎇oating␈α∞poin␈α␈t␈α∞arithmetic␈α∞is␈α∞su}cien␈α␈tly␈α∞accurate␈α∂to␈α∞giv␈α␈e␈ε/␈α∞exact␈ε"␈α∞results␈α∞in␈α∞all␈α∞the
␈β⊂∃␈↓ ↓H␈ε"computations␈α∂required␈α∞here.␈α→Most␈α∂binary␈α∂computers␈α∂will␈α∂be␈α∂able␈α∂to␈α∂meet␈α∞this
␈β⊂:␈↓ 
+␈ε+p
␈β⊂@␈↓ ↓H␈ε"requiremen␈α␈t␈α
when␈αall␈αof␈α
the␈αn␈α␈um␈α␈bers␈α
to␈αbe␈αdealt␈α
with␈αha␈α␈v␈α␈e␈α
the␈αform␈ε(␈αa␈ε"/␈↓ 
→␈ε"2␈↓ 
<␈ε",␈α
where
␈β⊂e␈↓ ∧v␈ε+p
␈β⊂k␈↓ ↓H␈ε(a␈ε"␈α
is␈α∞an␈α
in␈α␈teger,␈α∞0␈ε6␈α
∀␈ε(␈α
a␈ε"␈α<␈↓ ∧d␈ε"2␈↓ ¬π␈ε",␈α∞and␈α∞there␈α
are␈ε(␈α∞p␈ε"␈α
bits␈α∞of␈α∞precision␈α
in␈α∞⎇oating␈α
poin␈α␈t
␈β⊃⊗␈↓ ↓H␈ε"fractions.␈α⊗The␈α∞n␈α␈um␈α␈bers␈α∞(24,␈αε55)␈α∞in␈α∞these␈α∞routines␈α∞ma␈α␈y␈α
be␈α∞replaced␈α∞by␈α∞an␈α␈y␈α∞pair
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.6␈↓ 
v␈ε"173
␈β↓\␈↓ 	∪␈ε∞S␈α␈U␈α↓MMAR␈α}Y
␈βα"␈↓ ↓H␈ε"of␈αv␈α}alues␈α(␈↓ αi␈ε(j␈↓ αz␈ε",␈↓ β
␈ε(k␈↓ β≡␈ε")␈α
in␈αT␈α⎇able␈α3.2.2↑1,␈α
for␈↓ ε↓␈ε(k␈↓ ε ␈ε6∃␈ε"␈α
50;␈αthe␈α
constan␈α␈ts␈α31,␈α25,␈α
54,␈α21␈αsh␈α↓ould
␈βαM␈↓ ↓H␈ε"then␈αbe␈αreplaced␈αby␈↓ ∧π␈ε(k␈↓ ∧!␈ε6␈␈↓ ∧K␈ε(j␈↓ ∧\␈ε",␈↓ ∧q␈ε(j␈↓ ¬	␈ε"+␈αε1,␈↓ ¬Z␈ε(k␈↓ ¬t␈ε6␈␈ε"␈αε1,␈αand␈ε(␈αd␈ε"␈αrespectiv␈α␈ely,␈αwhere␈ε(␈αd␈ε"␈αis␈αrelativ␈α␈ely
␈βαZ␈↓ ∧z␈ε↓↓
␈βαy␈↓ ↓H␈ε"prime␈αto␈↓ αZ␈ε(k␈↓ αz␈ε"and␈ε(␈αd␈ε6␈α
→␈ε"␈α
0.382␈↓ ∧\␈ε(k␈↓ ∧p␈ε".
␈ββ$␈↓ α␈ε"Alth␈α↓ough␈αa␈αgreat␈αdeal␈α
is␈αkn␈α↓o␈α␈wn␈αabout␈αlinear␈αcongruen␈α␈tial␈αsequences␈αlik␈α␈e␈α
(1),
␈ββO␈↓ ↓H␈ε"v␈α␈ery␈αλlittle␈αλhas␈α	y␈α␈et␈αλbeen␈α	pro␈α␈v␈α␈ed␈αλabout␈αλthe␈α	randomness␈αλproperties␈α	of␈αλthe␈αλsubtractiv␈α␈e
␈ββz␈↓ ↓H␈ε"meth␈α↓od.␈α⊂Both␈αapproaches␈αseem␈αto␈αbe␈αreliable␈αin␈αpractice.
␈β∧%␈↓ α␈ε"Unfortunately,␈α⊃quite␈α⊃a␈α⊂bit␈α⊂of␈α⊂published␈α⊂material␈α⊃in␈α⊂existence␈α⊂at␈α⊂the␈α⊂time
␈β∧Q␈↓ ↓H␈ε"this␈α∩chapter␈α∩w␈α␈as␈α∩written␈α∩recommends␈α∩the␈α∩use␈α∩of␈α∩generators␈α∩that␈α∩violate␈α∩the
␈β∧|␈↓ ↓H␈ε"suggestions␈α	abo␈α␈v␈α␈e;␈α
and␈α	the␈α	m␈α↓ost␈α	comm␈α↓on␈α	generator␈α	in␈α	actual␈α	use,␈↓ 
!␈ε",␈α	is␈α	really
␈β∧}␈↓ 	B␈ε5RANDU
␈β¬'␈↓ ↓H␈ε"h␈α↓orrible␈α∂(cf.␈α∂Section␈α∂3.3.4).␈α→The␈α∂auth␈α↓ors␈α∂of␈α∂man␈α␈y␈α∂con␈α␈tributions␈α∂to␈α∂the␈α∂science
␈β¬R␈↓ ↓H␈ε"of␈αrandom␈α
n␈α␈um␈α␈ber␈α
generation␈αw␈α␈ere␈α
una␈α␈w␈α␈are␈α
that␈αparticular␈α
meth␈α↓ods␈α
they␈αw␈α␈ere
␈β¬⎇␈↓ ↓H␈ε"adv␈α␈ocating␈α∂w␈α␈ould␈α∞pro␈α␈v␈α␈e␈α∂to␈α∂be␈α∂inadequate.␈α→Perhaps␈α∂further␈α∂research␈α∂will␈α∞sh␈α↓o␈α␈w
␈βε)␈↓ ↓H␈ε"that␈αev␈α␈en␈αthe␈αrandom␈αn␈α␈um␈α␈ber␈αgenerators␈αrecommended␈αhere␈αare␈αunsatisfactory;
␈βεT␈↓ ↓H␈ε"w␈α␈e␈α⊃h␈α↓ope␈α⊃this␈α∩is␈α⊃n␈α↓ot␈α∩the␈α⊃case,␈α∪but␈α⊃the␈α∩history␈α⊃of␈α⊃the␈α∩subject␈α⊃w␈α␈arns␈α∩us␈α⊃to␈α⊃be
␈βε␈␈↓ ↓H␈ε"cautious.␈α∪The␈α
m␈α↓ost␈α
pruden␈α␈t␈α
policy␈α
for␈α∞a␈α
person␈α
to␈α
follo␈α␈w␈α
is␈α
to␈α
run␈α
each␈α
Mon␈α␈te
␈βπ*␈↓ ↓H␈ε"Carlo␈α∞program␈α∞at␈α∞least␈α∂t␈α␈wice␈α∞using␈α∞quite␈α∞di{eren␈α␈t␈α∂sources␈α∞of␈α∞random␈α∞n␈α␈um␈α␈bers,
␈βπU␈↓ ↓H␈ε"before␈α∂taking␈α∞the␈α∂answ␈α␈ers␈α∂of␈α∂the␈α∂program␈α∂seriously;␈α⊂this␈α∂n␈α↓ot␈α∂only␈α∂will␈α∂giv␈α␈e␈α∞an
␈βλ↓␈↓ ↓H␈ε"indication␈αof␈αthe␈αstabilit␈α␈y␈αof␈αthe␈αresults,␈αit␈αalso␈αwill␈αguard␈αagainst␈αthe␈αdanger␈αof
␈βλ,␈↓ ↓H␈ε"trusting␈αλin␈αλa␈αλgenerator␈αλwith␈αλhidden␈αλde|ciencies.␈α(Ev␈α␈ery␈αλrandom␈αλn␈α␈um␈α␈ber␈αλgenerator
␈βλW␈↓ ↓H␈ε"will␈αfail␈αin␈αat␈αleast␈αone␈αapplication.)
␈β	␈↓ α␈ε"Excellen␈α␈t␈α
bibliographies␈α∞of␈α
the␈α
pre-1972␈α
literature␈α∞on␈α
random␈α
n␈α␈um␈α␈ber␈α
gen-
␈β	7␈↓ ↓H␈ε"eration␈α∂ha␈α␈v␈α␈e␈α∂been␈α∂compiled␈α⊂by␈α∂Richard␈α∂E.␈↓ πβ␈ε"Nance␈α∂and␈α∂Claude␈↓ 	:␈ε"Ov␈α␈erstreet,␈α⊂Jr.,
␈β	b␈↓ ↓H␈ε/Computing␈α∩Reviews␈ε2␈α∪13␈ε"␈α∩(1972),␈α∃495↑508,␈α∀and␈α∩by␈α∪E.␈α∪R.␈↓ λb␈ε"So␈α␈w␈α␈ey,␈ε/␈α∀In␈α␈ternational
␈β
∞␈↓ ↓H␈ε/Stat.␈α∂Review␈ε2␈α⊂40␈ε"␈α⊂(1972),␈α⊂355↑371.␈α≠The␈α⊂period␈α⊂1972↑1976␈α∂is␈α⊂co␈α␈v␈α␈ered␈α⊂by␈α∂So␈α␈w␈α␈ey
␈β
9␈↓ ↓H␈ε"in␈ε/␈αIn␈α␈ternational␈αStat.␈αReview␈ε2␈α46␈ε"␈α(1978),␈α89↑102.
␈β
d␈↓ α␈ε"F␈α⎇or␈α∂a␈α∞detailed␈α∂study␈α∞of␈α∂the␈α∞use␈α∂of␈α∞random␈α∂n␈α␈um␈α␈bers␈α∞in␈α∂n␈α␈umerical␈α∞analysis,
␈β∂␈↓ ↓H␈ε"see␈α∞J.␈α∂M.␈↓ αg␈ε"Hammersley␈α∂and␈α∞D.␈α∂C.␈↓ ¬e␈ε"Handscom␈α␈b,␈ε/␈α∂Mon␈α␈te␈α∞Carlo␈α∂Meth␈α↓ods␈ε"␈α∞(London:
␈β:␈↓ ↓H␈ε"Meth␈α␈uen,␈α∞1964).␈α⊗This␈α∞bo␈α↓ok␈α∞sh␈α↓o␈α␈ws␈α∞that␈α∞some␈α∞n␈α␈umerical␈α∞meth␈α↓ods␈α∞are␈α∞enhanced
␈βf␈↓ ↓H␈ε"by␈α∂using␈α∂n␈α␈um␈α␈bers␈α⊂that␈α∂are␈α⊂\quasi-random,"␈α⊂designed␈α∂speci|cally␈α⊂for␈α∂a␈α∂certain
␈β⊃␈↓ ↓H␈ε"purpose␈α(n␈α↓ot␈αnecessarily␈αsatisfying␈αthe␈αstatistical␈αtests␈αw␈α␈e␈αha␈α␈v␈α␈e␈αdiscussed).
␈β<␈↓ α␈ε"Ev␈α␈ery␈αreader␈αis␈αurged␈αto␈αw␈α␈ork␈αexercise␈α6␈αin␈αthe␈αfollo␈α␈wing␈αset␈αof␈αproblems.
␈β
:␈↓ ↓H␈ε=E␈α␈XERCISES
␈β∞	␈↓ ↓g␈ε31.␈↓ α␈ε#[␈ε)21␈↓ α;␈ε#]␈α⊗W␈α⎇rite␈αa␈↓ ∧∂␈ε#sub␈α␈rou␈α␈tine␈αwith␈αth␈α␈e␈αfollo␈α␈wing␈αc␈α␈har␈α␈acteristics,␈αusin␈α␈g␈αmethod␈α
(1):
␈β∞␈↓ βQ␈ε∃MIX
␈β∞N␈↓ αO␈ε#C␈α↓a␈α␈ll␈α↓in␈α␈g␈αsequ␈α␈en␈α␈ce:
␈β∞P␈↓ ∧k␈ε∃JMP␈α⊃RANDI
␈β∞⎇␈↓ αN␈ε#En␈α}try␈αco␈α␈nd␈α␈i␈α↓tion␈α␈s:␈↓ ∧k␈ε#r␈α␈A␈↓ ¬→␈ε#=␈↓ ¬C␈ε)k␈↓ ¬V␈ε#,␈αa␈αp␈α␈ositi␈α↓v␈α}e␈αin␈α␈teg␈α␈er␈α<␈α
5␈α␈000␈α␈.
␈β∂,␈↓ αb␈ε#Exit␈αco␈α␈nd␈α␈i␈α↓tion␈α␈s:␈↓ ∧k␈ε#r␈α␈A␈↓ ¬→␈ε7␈ ␈ε#␈αa␈αran␈α␈do␈α␈m␈αin␈α␈teg␈α␈er␈↓ πI␈ε)Y␈↓ πd␈ε#,␈α1␈ε7␈α	∀␈↓ λ<␈ε)Y␈↓ λ`␈ε7∀␈↓ 	␈ε)k␈↓ 	≥␈ε#,␈αwith␈αe␈α␈ach␈α
i␈α↓n␈α}tege␈α␈r
␈β∂S␈↓ ∧k␈ε#a␈α␈bo␈α␈ut␈αeq␈α␈ua␈α␈l␈α↓ly␈αp␈α␈rob␈α␈ab␈α␈l␈α↓e␈α␈;␈↓ πM␈ε#rX␈↓ π{␈ε#=?;␈αo␈α}v␈α␈er⎇␈α␈o␈α␈w␈αo{␈α␈.
␈β⊂!␈↓ ↓;␈ε↓x
␈β⊂#␈↓ ↓c␈ε32.␈↓ α␈ε#[␈ε)15␈↓ α;␈ε#]␈α⊗S␈α␈ome␈α∞peo␈α␈ple␈α∂h␈α␈a␈α␈v␈α␈e␈α∞bee␈α␈n␈α∂afra␈α␈id␈α∂th␈α␈at␈α∂co␈α␈mpu␈α␈ters␈α∂will␈α∂somed␈α␈a␈α␈y␈α∞tak␈α}e␈α∂o␈α␈v␈α␈e␈α␈r␈α∂the
␈β⊂K␈↓ ↓H␈ε#w␈α␈o␈α␈rl␈α↓d␈α␈;␈α⊂b␈α␈ut␈α∞th␈α␈ey␈α∞a␈α␈re␈α∞reassu␈α␈red␈α
by␈α∞th␈α␈e␈α∞sta␈α␈temen␈α}t␈α∞tha␈α␈t␈α∞a␈α∞mac␈α␈hine␈α∞c␈α␈an␈α␈n␈α↓ot␈α∞d␈α␈o␈α∞a␈α␈n␈α␈yth␈α␈ing
␈β⊂r␈↓ ↓H␈ε#re␈α␈all␈α↓y␈α∂new,␈α∩s␈α␈i␈α↓n␈α␈ce␈α⊂it␈α⊃is␈α⊂on␈α␈ly␈α⊂ob␈α␈eying␈α∂the␈α⊂co␈α␈mman␈α␈ds␈α⊂o␈α␈f␈α⊃its␈α⊂maste␈α␈r,␈α∩the␈α⊂p␈α␈rog␈α␈ramm␈α␈er.
␈β⊃~␈↓ ↓H␈ε#La␈α␈dy␈↓ α≡␈ε#Lo␈α␈v␈α␈elac␈α␈e␈αwrote␈αin␈α1␈α␈84␈α␈4,␈α\Th␈α␈e␈αAna␈α␈lytical␈αEn␈α␈gine␈αha␈α␈s␈αn␈α↓o␈αp␈α␈reten␈α␈si␈α↓o␈α␈ns␈αto␈ε0␈αo␈α␈ri␈α↓g␈α␈i␈α↓n␈α␈ate
␈β∪(

␈β↓U␈↓ ↓H␈ε"174␈↓ 
}␈ε"3.6
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα&␈↓ ↓H␈ε#a␈α␈n␈α␈y␈α␈thing␈α␈.␈α↔It␈α
can␈α
d␈α␈o␈ε0␈α∞wh␈α␈atev␈α}er␈α∞w␈α␈e␈α
kno␈α␈w␈α
h␈α↓o␈α␈w␈α
to␈α
orde␈α␈r␈α∞it␈ε#␈α∞to␈α
p␈α␈erform."␈α⊗Her␈α
state␈α␈men␈α}t
␈βαN␈↓ ↓H␈ε#h␈α␈as␈α∞b␈α␈een␈α
furth␈α␈er␈α∞elab␈α␈orat␈α␈ed␈α∞b␈α␈y␈α∞ma␈α␈n␈α␈y␈α
ph␈α␈i␈α↓lo␈α␈soph␈α␈ers.␈α_Discu␈α␈ss␈α∞th␈α␈i␈α↓s␈α∞to␈α␈pic,␈α∂with␈α
rand␈α␈om
␈βαu␈↓ ↓H␈ε#n␈α}um␈α␈b␈α␈er␈αge␈α␈nera␈α␈tors␈αin␈αm␈α␈i␈α↓n␈α␈d.
␈ββ2␈↓ ↓g␈ε33.␈↓ α␈ε#[␈ε)32␈↓ α;␈ε#]␈α⊗(␈ε0A␈↓ β
␈ε0dice␈αgame␈α␈.␈ε#␈α↓)␈α≥W␈α⎇ri␈α↓t␈α␈e␈α
a␈α
pro␈α␈gram␈αtha␈α␈t␈α∞sim␈α␈u␈α␈lates␈↓ λ.␈ε#a␈α
ro␈α␈ll␈α∞o␈α␈f␈α∞t␈α␈w␈α␈o␈α
d␈α␈ice,␈α∞ea␈α␈ch␈α
o␈α␈f
␈ββY␈↓ ↓H␈ε#wh␈α␈ich␈αtak␈α}es␈αon␈αth␈α␈e␈αv␈α}alu␈α␈es␈α1,␈α2␈α␈,␈↓ ¬∀␈ε#.␈αε.␈α¬.␈↓ ¬@␈ε#,␈α6␈αwith␈αeq␈α␈ua␈α␈l␈αp␈α␈roba␈α␈bilit␈α␈y.␈α⊂If␈αthe␈αto␈α␈tal␈αi␈α↓s␈α7␈αo␈α␈r␈α1␈α␈1␈αon
␈β∧↓␈↓ ↓H␈ε#th␈α␈e␈α|rst␈αroll,␈αthe␈αgam␈α␈e␈αis␈αwo␈α␈n;␈αa␈αtota␈α␈l␈αof␈α2,␈α3,␈αo␈α␈r␈α1␈α␈2␈αlose␈α␈s;␈αan␈α␈d␈αo␈α␈n␈αan␈α␈y␈αo␈α␈ther␈αtota␈α␈l␈α↓,␈αcall
␈β∧(␈↓ ↓H␈ε#th␈α␈at␈αtotal␈αthe␈α\p␈α␈oin␈α␈t"␈αan␈α␈d␈αcon␈α}ti␈α↓n␈α}ue␈αrolling␈αdice␈αun␈α}til␈α
either␈αa␈α
7␈αo␈α␈ccur␈α␈s␈α
(a␈αl␈α↓o␈α␈ss)␈α
or␈αthe
␈β∧P␈↓ ↓H␈ε#p␈α␈oin␈α␈t␈αo␈α␈ccu␈α␈rs␈αaga␈α␈i␈α↓n␈α
(a␈αwin).
␈β∧z␈↓ α␈ε#Pla␈α␈y␈αten␈αga␈α␈mes.␈α⊂The␈αresu␈α␈l␈α↓t␈αof␈αeach␈αro␈α␈ll␈αof␈αth␈α␈e␈αdice␈αsh␈α↓o␈α␈uld␈αbe␈αp␈α␈ri␈α↓n␈α}ted␈αin␈αthe␈αform
␈β¬"␈↓ ↓H␈ε)m␈α¬n␈ε#,␈α∞where␈ε)␈α
m␈ε#␈α
a␈α␈nd␈ε)␈α
n␈ε#␈α
are␈α
th␈α␈e␈α∞c␈α␈on␈α␈te␈α␈n␈α␈ts␈α
of␈α
the␈α
t␈α␈w␈α␈o␈α
d␈α␈i␈α↓ce␈α␈,␈α∞f␈α↓o␈α␈ll␈α↓o␈α}we␈α␈d␈α
by␈α
so␈α␈me␈α
ap␈α␈pro␈α␈priate
␈β¬I␈↓ ↓H␈ε#c␈α␈omme␈α␈n␈α␈t␈α(li␈α↓k␈α}e␈α\sn␈α␈ak␈α}e␈αey␈α␈es"␈α
or␈α\little␈αJo␈α␈e"␈αor␈α\␈α␈the␈αh␈α␈ard␈α
wa␈α}y",␈αetc␈α␈.␈α↓).
␈βεε␈↓ ↓g␈ε34.␈↓ α␈ε#[␈ε)40␈↓ α;␈ε#]␈α⊗(␈ε0S␈α␈olitaire␈α	or␈α	p␈α␈atien␈α␈ce.␈ε#)␈α⊃So␈α␈me␈α	pe␈α␈op␈α␈l␈α↓e␈α	s␈α␈pen␈α␈d␈α	a␈αλl␈α↓o␈α␈t␈α	of␈α	v␈α}a␈α␈l␈α↓u␈α␈ab␈α␈l␈α↓e␈αλti␈α↓m␈α␈e␈α	pla␈α␈y␈α␈ing␈α	c␈α␈ard
␈βε-␈↓ ↓H␈ε#g␈α␈ame␈α␈s␈α
of␈α
so␈α␈li␈α↓ta␈α␈i␈α↓r␈α␈e,␈α
and␈α	p␈α␈erha␈α␈ps␈α	au␈α␈toma␈α␈ti␈α↓o␈α␈n␈α
will␈α
ma␈α␈k␈α␈e␈α	an␈α	i␈α↓m␈α␈po␈α␈rtan␈α␈t␈α	inroa␈α␈d␈α	i␈α↓n␈α	th␈α␈i␈α↓s␈α	area␈α␈.
␈βεU␈↓ ↓H␈ε#W␈α⎇rite␈αa␈αp␈α␈rogra␈α␈m␈αtha␈α␈t␈α→(a)␈αsh␈α␈u␈α␈␈␈es␈αa␈αsim␈α␈u␈α␈lated␈α
deck␈α
of␈αca␈α␈rds;␈α→(b)␈αpla␈α␈y␈α␈s␈αsome␈α
common
␈βε|␈↓ ↓H␈ε#g␈α␈ame␈α
of␈αsolitaire␈αb␈α␈ased␈α
on␈α
the␈α
ord␈α␈er␈αof␈αth␈α␈e␈αca␈α␈rds␈αin␈α
the␈α
deck␈α␈;␈α→(c)␈αp␈α␈rin␈α␈ts␈αou␈α␈t␈αth␈α␈e␈αresu␈α␈lt
␈βπ$␈↓ ↓H␈ε#o␈α␈f␈α∞th␈α␈e␈α
game␈α␈,␈α∂i.e.,␈α∞h␈α↓o␈α␈w␈α
close␈α
th␈α␈e␈α∞p␈α␈rog␈α␈ram␈α
cam␈α␈e␈α
to␈α
w␈α↓in␈α␈ning␈α␈.␈α⊗Sev␈α}eral␈α
gam␈α␈es␈α
sh␈α↓o␈α␈uld␈α
be
␈βπL␈↓ ↓H␈ε#p␈α␈la␈α␈y␈α␈ed␈α␈.␈α∂The␈αp␈α␈rog␈α␈ram␈αmig␈α␈h␈α␈t␈αbe␈α
set␈αup␈α
to␈α\ch␈α␈ea␈α␈t"␈αup␈α␈on␈α
requ␈α␈est.
␈βλλ␈↓ ↓g␈ε35.␈↓ α␈ε#[␈ε)46␈↓ α;␈ε#]␈α⊗(␈ε0Crea␈α␈tiv␈α␈e␈αλwriting␈αλb␈α␈y␈αλc␈α␈omp␈α␈uter.␈ε#)␈α
A␈αλtelev␈α␈i␈α↓sion␈απpro␈α␈gra␈α␈m␈αλen␈α␈t␈α␈i␈α↓tled␈απ\Th␈α␈e␈αλThink␈α␈ing
␈βλ/␈↓ ↓H␈ε#M␈α␈ach␈α␈ine,"␈α⊂bro␈α␈adc␈α␈ast␈α∂by␈α∂th␈α␈e␈α⊂CBS␈α∂telev␈α␈i␈α↓sion␈↓ εb␈ε#n␈α␈et␈α␈w␈α␈ork␈α∂o␈α␈n␈α∂Octob␈α␈er␈α∂26,␈α⊃1␈α␈960␈α␈,␈α⊃featu␈α␈red
␈βλW␈↓ ↓H␈ε#(a␈α␈m␈α↓on␈α␈g␈α⊃oth␈α␈er␈α⊃thin␈α␈gs)␈α⊃t␈α␈w␈α␈o␈α⊃W␈α}e␈α␈stern-st␈α␈y␈α␈l␈α↓e␈α⊃p␈α␈la␈α␈ylets␈α⊃th␈α␈at␈α⊃w␈α␈ere␈α⊃written␈α⊂by␈α⊃a␈α⊃c␈α␈omp␈α␈ute␈α␈r
␈βλ␈␈↓ ↓H␈ε#p␈α␈rog␈α␈ram.␈α∂Here␈α
are␈αth␈α␈e␈αt␈α␈wo␈α
scripts␈αa␈α␈s␈αthey␈α
w␈α␈ere␈αprin␈α}ted␈αo␈α␈ut␈αb␈α␈y␈αthe␈α
comp␈α␈ute␈α␈r:
␈β	B␈↓ ↓H␈ε Saga␈ε8␈αq␈ε?␈α↓1.␈α~(The␈αgun␈α
is␈α
in␈αthe␈α
right␈αhand;␈α
the␈α
money␈αis␈α
in␈αthe␈α
le$␈αhand;␈α
the␈α
glass␈αis
␈β	b␈↓ ↓H␈ε?on␈α
the␈αtable;␈αthe␈α
bottle␈αis␈α
on␈αthe␈α
table;␈αthe␈αholster␈α
is␈α
on␈αthe␈↓ λI␈ε?robber;␈αthe␈↓ 	{␈ε?sheri{'s␈α
gun
␈β
α␈↓ ↓H␈ε?is␈αin␈αthe␈αsheri{'s␈αright␈αhand;␈αthe␈αsheri{'s␈αholster␈αis␈αon␈αthe␈αsheri{.)
␈β
,␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?(The␈α⊂robber␈α∂is␈α⊂at␈α∂the␈α⊂windo␈α␈w.)␈α~Go␈α∂to␈α⊂do␈α↓or;␈α⊃open␈α∂do␈α↓or;␈α∩go␈α∂thru␈α∂do␈α↓or;
␈β
M␈↓ αa␈ε?close␈αdo␈α↓or;␈αgo␈αto␈αcorner;␈αput␈αmoney␈αdo␈α␈wn␈αat␈αcorner;␈αgo␈αto␈αtable;␈αput␈αgun
␈β
m␈↓ αa␈ε?on␈αtable;␈αsit␈α
and␈α|dgit;␈αsit␈α
at␈αtable;␈αpick␈α
up␈αglass␈α
with␈α
right␈αhand␈α
(empt␈α␈y);
␈β∞␈↓ αa␈ε?put␈α∂glass␈α∂on␈α∂table;␈α⊃pick␈α∂up␈α∂bottle␈α∂with␈α∂right␈α∂hand;␈α⊂pour;␈α⊂put␈α∂bottle␈α∂on
␈β.␈↓ αa␈ε?table;␈α⊃pick␈α∂up␈α∞glass␈α∂with␈α∂right␈α∂hand;␈α⊃tak␈α␈e␈α∞a␈α∂drink␈α∂from␈α∂glass;␈α⊃put␈α∞glass
␈βN␈↓ αa␈ε?on␈α∞table;␈α∞pick␈α
up␈α∞bottle␈α
with␈α∞right␈α
hand;␈α∂sit␈α
at␈α∞table;␈α∞sit␈α
at␈α∞table;␈α∞go␈α
to
␈βo␈↓ αa␈ε?corner;␈α∞go␈αto␈α
windo␈α␈w;␈α∞go␈αto␈α
table;␈α∞put␈αbottle␈α
on␈α
table;␈α
sit␈α
and␈α
|dgit;␈α
sit
␈β∂␈↓ αa␈ε?at␈αtable;␈αsit␈αand␈α|dgit;␈αgo␈αto␈α
windo␈α␈w;␈αgo␈α
to␈αtable;␈αpick␈αup␈αglass␈αwith␈α
right
␈β0␈↓ αa␈ε?hand.
␈βZ␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?(The␈α⊂sheri{␈α∂is␈α∂at␈α⊂the␈α∂windo␈α␈w.)␈α~See␈α∂robber;␈α⊃(robber␈α⊂sees␈α∂sheri{);␈α⊃go␈α∂to
␈βz␈↓ αa␈ε?do␈α↓or.
␈β
$␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Put␈αglass␈αon␈αtable;␈αpick␈αup␈αgun␈αwith␈αright␈αhand;␈αcheck␈αgun.
␈β
N␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?W␈α⎇ait;␈αopen␈αdo␈α↓or;␈αsee␈αrobber;␈α(robber␈αsees␈αsheri{);␈αgo␈αthru␈αdo␈α↓or.
␈β
x␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Go␈αto␈αwindo␈α␈w;␈αaim;␈α|re;␈αSHERIFF␈αNICKED.
␈β∞"␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Go␈αto␈αwindo␈α␈w;␈αaim;␈α|re;␈αMISSED;␈αgo␈αto␈αdo␈α↓or;␈αgo␈αto␈αwindo␈α␈w.
␈β∞L␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Go␈αto␈αdo␈α↓or;␈αaim;␈αaim.
␈β∞w␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Aim;␈α|re;␈αMISSED.
␈β∂!␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Fire;␈αSHERIFF␈αNICKED.
␈β∂K␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Go␈αto␈αdo␈α↓or;␈αaim;␈α|re;␈αMISSED;␈αgo␈αthru␈αdo␈α↓or;␈αaim.
␈β∂u␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Aim;␈α|re;␈αMISSED;␈αaim;␈α|re;␈αMISSED.
␈β⊂∨␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Fire;␈αMISSED;␈αgo␈αto␈αwindo␈α␈w;␈αaim;␈α|re;␈αMISSED.
␈β⊂I␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Aim;␈α|re;␈αMISSED;␈αaim;␈α|re;␈αMISSED;␈αaim;␈α|re;␈αSHERIFF␈αNICKED.
␈β⊂s␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Aim;␈α|re;␈αROBBER␈αHIT.
␈β⊃≥␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Drop␈αgun;␈αrobber␈αdies.
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.6␈↓ 
v␈ε"175
␈β↓\␈↓ 	∪␈ε∞S␈α␈U␈α↓MMAR␈α}Y
␈βλ*␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Put␈α
gun␈α	in␈α
holster;␈α
go␈α	to␈α
table;␈α
pick␈α
up␈α	glass␈α
with␈α	right␈α
hand␈α	(empt␈α␈y);␈α
tak␈α␈e
␈βλJ␈↓ αa␈ε?glass␈αfrom␈α
right␈α
hand␈αwith␈α
le$␈αhand;␈αpick␈α
up␈α
bottle␈αwith␈α
right␈αhand;␈α
pour;
␈βλj␈↓ αa␈ε?put␈α
bottle␈α
on␈α	table;␈αtak␈α␈e␈α	glass␈α
from␈α
le$␈α
hand␈α	with␈α
right␈α
hand;␈α
tak␈α␈e␈α
a␈α	drink
␈β	␈↓ αa␈ε?from␈αglass;␈αtak␈α␈e␈αglass␈αfrom␈αright␈αhand␈αwith␈αle$␈αhand;␈αpick␈αup␈αbottle␈αwith
␈β	+␈↓ αa␈ε?right␈αhand;␈αpour;␈αput␈αbottle␈αon␈αtable;␈αtak␈α␈e␈αglass␈αfrom␈αle$␈αhand␈αwith␈αright
␈β	L␈↓ αa␈ε?hand;␈α∂tak␈α␈e␈α∞a␈α
drink␈α∞from␈α∞glass;␈α∂put␈α
glass␈α∞on␈α∞table;␈α∂go␈α
to␈α∞corner;␈α∂pick␈α
up
␈β	l␈↓ αa␈ε?money␈αwith␈αright␈αhand;␈αgo␈αto␈αdo␈α↓or;␈αgo␈αthru␈αdo␈α↓or;␈αclose␈αdo␈α↓or.␈α⊂CURT␈α⎇AIN.
␈β
)␈↓ ↓H␈ε Saga␈ε8␈αq␈ε?␈α↓2.␈α~(The␈αgun␈α
is␈α
in␈αthe␈α
right␈αhand;␈α
the␈α
money␈αis␈α
in␈αthe␈α
le$␈αhand;␈α
the␈α
glass␈αis
␈β
I␈↓ ↓H␈ε?on␈α
the␈αtable;␈αthe␈α
bottle␈αis␈α
on␈αthe␈α
table;␈αthe␈αholster␈α
is␈α
on␈αthe␈α
robber;␈αthe␈αsheri{'s␈α
gun
␈β
j␈↓ ↓H␈ε?is␈αin␈αthe␈αsheri{'s␈αright␈αhand;␈αthe␈αsheri{'s␈αholster␈αis␈αon␈αthe␈αsheri{.)
␈β∪␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?(The␈α⊂robber␈α∂is␈α⊂at␈α∂the␈α⊂windo␈α␈w.)␈α~Go␈α∂to␈α⊂do␈α↓or;␈α⊃open␈α∂do␈α↓or;␈α∩go␈α∂thru␈α∂do␈α↓or;
␈β3␈↓ αa␈ε?close␈α∞do␈α↓or;␈α∞go␈α
to␈α
corner;␈α∞put␈α∞money␈α
do␈α␈wn␈α
at␈α∞corner;␈α∞go␈α
to␈α
windo␈α␈w;␈α∞put
␈βS␈↓ αa␈ε?gun␈αdo␈α␈wn␈αat␈αwindo␈α␈w;␈αlean␈αon␈αwindo␈α␈w␈αand␈αlo␈α↓ok;␈αlean␈αon␈αwindo␈α␈w␈αand␈αlo␈α↓ok;
␈βt␈↓ αa␈ε?go␈α⊂to␈α∂corner;␈α∩count␈α∂money;␈α∩go␈α∂to␈α⊂table;␈α⊃pick␈α⊂up␈α⊂glass␈α∂with␈α⊂right␈α∂hand
␈β∀␈↓ αa␈ε?(empt␈α␈y);␈α⊂tak␈α␈e␈α∞glass␈α∂from␈α∞right␈α∂hand␈α∞with␈α∂le$␈α∞hand;␈α⊂pick␈α∞up␈α∂bottle␈α∞with
␈β5␈↓ αa␈ε?right␈αhand;␈αpour;␈αput␈αbottle␈αon␈αtable;␈αtak␈α␈e␈αglass␈αfrom␈αle$␈αhand␈αwith␈αright
␈βU␈↓ αa␈ε?hand;␈αtak␈α␈e␈α
a␈α
drink␈αfrom␈α
glass;␈αput␈α
glass␈α
on␈α
table;␈αpick␈α
up␈α
bottle␈α
with␈α
right
␈βu␈↓ αa␈ε?hand;␈α
pour;␈α
go␈α
to␈αcorner;␈α
put␈α
bottle␈αdo␈α␈wn␈α
at␈αcorner;␈α
go␈α
to␈α
windo␈α␈w;␈αpick
␈β
⊗␈↓ αa␈ε?up␈α∞gun␈α
with␈α
right␈α
hand;␈α∞check␈α
gun;␈α∞put␈α∞gun␈α
in␈α
holster;␈α∞go␈α
to␈α∞table;␈α
pick
␈β
6␈↓ αa␈ε?up␈αglass␈αwith␈αright␈αhand;␈αtak␈α␈e␈αa␈αdrink␈αfrom␈αglass;␈αgo␈αto␈αwindo␈α␈w;␈αput␈αglass
␈β
W␈↓ αa␈ε?do␈α␈wn␈αat␈αwindo␈α␈w.
␈β
␈␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?(The␈α⊂sheri{␈α∂is␈α∂at␈α⊂the␈α∂windo␈α␈w.)␈α~See␈α∂robber;␈α⊃(robber␈α⊂sees␈α∂sheri{);␈α⊃go␈α∂to
␈β∞ ␈↓ αa␈ε?do␈α↓or.
␈β∞H␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?T␈α⎇ak␈α␈e␈αgun␈αfrom␈αholster␈αwith␈αright␈α
hand;␈αcheck␈α
gun;␈αgo␈αto␈α
do␈α↓or;␈αcheck␈α
gun;
␈β∞i␈↓ αa␈ε?put␈αgun␈αdo␈α␈wn␈αat␈αdo␈α↓or.
␈β∂⊃␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Open␈αdo␈α↓or;␈αsee␈αrobber;␈α(robber␈αsees␈αsheri{);␈αgo␈αthru␈αdo␈α↓or;␈αgo␈αto␈αwindo␈α␈w.
␈β∂:␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Pick␈αup␈αgun␈αwith␈αright␈αhand.
␈β∂b␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Go␈αto␈αtable.
␈β⊂␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Aim;␈α∂|re;␈α∞MISSED;␈α
aim;␈α∂|re;␈α∞SHERIFF␈α∞HIT;␈α
blo␈α␈w␈α∞out␈α
barrel;␈α∞put␈α∞gun␈α
in
␈β⊂+␈↓ αa␈ε?holster.
␈β⊂T␈↓ ↓H␈ε?SHERIFF:␈↓ αa␈ε?Drop␈αgun;␈αsheri{␈αdies.
␈β⊂⎇␈↓ ↓H␈ε?ROBBER:␈↓ αa␈ε?Go␈α
to␈α
corner;␈α
pick␈α
up␈α
money␈α
with␈α
right␈α
hand;␈α
go␈α
to␈α
do␈α↓or;␈α∞go␈α
thru␈αdo␈α↓or;
␈β⊃≥␈↓ αa␈ε?close␈αdo␈α↓or.␈α⊂CURT␈α⎇AIN.
␈β∪(

␈β↓U␈↓ ↓H␈ε"176␈↓ 
}␈ε"3.6
␈β↓\␈↓ α=␈ε∞RANDOM␈α
NU␈α↓MB␈α␈E␈α↓RS
␈βα&␈↓ α␈ε#A␈α∞carefu␈α␈l␈α∂rea␈α␈ding␈α∞o␈α␈f␈α∂th␈α␈e␈α∞ab␈α␈o␈α␈v␈α␈e␈α∞scrip␈α␈ts␈α∂re␈α␈v␈α␈eals␈α∞the␈α∞h␈α␈i␈α↓g␈α␈hly␈α∞in␈α␈te␈α␈nse␈α∞dr␈α␈ama␈α∞p␈α␈resen␈α}t
␈βαN␈↓ ↓H␈ε#h␈α␈ere.␈α∂Th␈α␈e␈αc␈α␈omp␈α␈uter␈α
pro␈α␈gra␈α␈m␈αw␈α␈as␈α
care␈α␈f␈α↓u␈α␈l␈αto␈α
k␈α␈ee␈α␈p␈α
track␈α
of␈α
the␈α
locatio␈α␈ns␈αo␈α␈f␈αea␈α␈ch␈α
pla␈α␈y␈α}er,
␈βαu␈↓ ↓H␈ε#th␈α␈e␈α
con␈α}ten␈α␈ts␈α
of␈α
his␈α
han␈α␈ds␈α␈,␈α∂etc␈α␈.␈α⊗Actions␈α
tak␈α}en␈α
b␈α␈y␈α
the␈α
pla␈α␈y␈α}ers␈α
we␈α␈re␈α∞ra␈α␈nd␈α␈om,␈α∞go␈α}v␈α␈ern␈α␈ed
␈ββ≥␈↓ ↓H␈ε#b␈α␈y␈α
certa␈α␈i␈α↓n␈α	prob␈α␈ab␈α␈il␈α↓ities;␈αth␈α␈e␈α
prob␈α␈ab␈α␈il␈α↓it␈α␈y␈α
of␈α
a␈α
fo␈α↓olish␈α
ac␈α␈ti␈α↓o␈α␈n␈α
w␈α␈as␈α
i␈α↓n␈α␈crea␈α␈sed␈α
d␈α␈epe␈α␈nd␈α␈i␈α↓n␈α␈g␈α
on
␈ββD␈↓ ↓H␈ε#ho␈α␈w␈α	m␈α␈u␈α␈ch␈α	th␈α␈at␈α	pla␈α␈y␈α}er␈α	had␈αλhad␈αλto␈α	drin␈α␈k␈α	an␈α␈d␈α	on␈αλh␈α↓o␈α␈w␈α	o$e␈α␈n␈α	he␈α	h␈α␈ad␈α	b␈α␈een␈α	n␈α␈ick␈α␈ed␈αλi␈α↓n␈αλa␈α	sh␈α↓o␈α␈t.
␈ββl␈↓ ↓H␈ε#Th␈α␈e␈α
rea␈α␈der␈α
will␈α
be␈α
a␈α␈ble␈α
to␈αded␈α␈uc␈α␈e␈α
furth␈α␈er␈α
p␈α␈rope␈α␈rti␈α↓e␈α␈s␈α
of␈α
th␈α␈e␈α
pro␈α␈gram␈αby␈αstud␈α␈ying␈αthe
␈β∧∀␈↓ ↓H␈ε#sa␈α␈mp␈α␈l␈α↓e␈αsc␈α␈ri␈α↓p␈α␈ts.
␈β∧<␈↓ α␈ε#Of␈αcou␈α␈rse,␈α
e␈α␈v␈α␈en␈αthe␈αb␈α␈est␈αscripts␈αa␈α␈re␈αrewritten␈αb␈α␈efore␈αth␈α␈ey␈αa␈α␈re␈αpro␈α␈du␈α␈ced␈α␈,␈α
an␈α␈d␈αth␈α␈is
␈β∧c␈↓ ↓H␈ε#is␈αespec␈α␈i␈α↓a␈α␈ll␈α↓y␈αtru␈α␈e␈α
wh␈α␈en␈αan␈αinex␈α␈pe␈α␈ri␈α↓e␈α␈nced␈αwriter␈αha␈α␈s␈α
pr␈α␈epa␈α␈red␈αthe␈αorigin␈α␈al␈α
dr␈α␈a$.␈α∀Here
␈β¬␈↓ ↓H␈ε#a␈α␈re␈αthe␈αs␈α␈cripts␈αjust␈αa␈α␈s␈αthey␈α
w␈α␈ere␈αac␈α␈tually␈αu␈α␈sed␈αin␈α
the␈αsho␈α␈w:
␈β¬H␈↓ ↓H␈ε Saga␈ε8␈αq␈ε?1.␈α$Music␈αup.
␈β¬l␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αpeering␈αthru␈αwindo␈α␈w␈αof␈αshack.
␈βε⊂␈↓ ↓H␈ε?CU␈↓ α
␈ε?Robber's␈αface.
␈βε4␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αentering␈αshack.
␈βεX␈↓ ↓H␈ε?CU␈↓ α
␈ε?Robber␈αsees␈αwhisk␈α␈ey␈αbottle␈αon␈αtable.
␈βε|␈↓ ↓H␈ε?CU␈↓ α
␈ε?Sheri{␈αoutside␈αshack.
␈βπ ␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αsees␈αsheri{.
␈βπD␈↓ ↓H␈ε?LS␈↓ α
␈ε?Sheri{␈αin␈αdo␈α↓orw␈α␈a␈α␈y␈αo␈α␈v␈α␈er␈αshoulder␈αof␈αrobber,␈αboth␈αdra␈α␈w.
␈βπh␈↓ ↓H␈ε?MS␈↓ α
␈ε?Sheri{␈αdra␈α␈wing␈αgun.
␈βλ␈↓ ↓H␈ε?LS␈↓ α
␈ε?Sho␈α↓oting␈αit␈αout.␈α⊂Robber␈αgets␈αshot.
␈βλ0␈↓ ↓H␈ε?MS␈↓ α
␈ε?Sheri{␈αpicking␈αup␈αmoney␈αbags.
␈βλT␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αstaggering.
␈βλx␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αdying.␈α⊂F␈α⎇alls␈αacross␈αtable,␈αa$er␈αtrying␈αto␈αtak␈α␈e␈αlast␈αshot␈αat␈αsheri{.
␈β	≤␈↓ ↓H␈ε?MS␈↓ α
␈ε?Sheri{␈αw␈α␈alking␈αthru␈αdo␈α↓orw␈α␈a␈α␈y␈αwith␈αmoney.
␈β	@␈↓ ↓H␈ε?MS␈↓ α
␈ε?of␈αλrobber's␈αλbody,␈αλno␈α␈w␈αλstill,␈α	lying␈αλacross␈αλtable␈αλtop.␈α∂Camera␈αλdollies␈αλback.␈α∂(Laughter)
␈β	p␈↓ ↓H␈ε Saga␈ε8␈αq␈ε?2.␈α$Music␈αup.
␈β
∀␈↓ ↓H␈ε?CU␈↓ α
␈ε?of␈αwindo␈α␈w.␈α⊂Robber␈αappears.
␈β
8␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αentering␈αshack␈αwith␈αt␈α␈w␈α␈o␈αsacks␈αof␈αmoney.
␈β
\␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αputs␈αmoney␈αbags␈αon␈αbarrel.
␈β␈↓ ↓H␈ε?CU␈↓ α
␈ε?Robber←sees␈αwhisk␈α␈ey␈αon␈αtable.
␈β$␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αpouring␈αhimself␈αa␈αdrink␈αat␈αtable.␈α⊂Goes␈αto␈αcount␈αmoney.␈α⊂Laughs.
␈βH␈↓ ↓H␈ε?MS␈↓ α
␈ε?Sheri{␈αoutside␈αshack.
␈βl␈↓ ↓H␈ε?MS␈↓ α
␈ε?thru␈αwindo␈α␈w.
␈β⊂␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αsees␈αsheri{␈αthru␈αwindo␈α␈w.
␈β4␈↓ ↓H␈ε?LS␈↓ α
␈ε?Sheri{␈αentering␈αshack.␈α⊂Dra␈α␈w.␈α⊂Sho␈α↓ot␈αit␈αout.
␈βX␈↓ ↓H␈ε?CU␈↓ α
␈ε?Sheri{.␈α⊂W␈α⎇rithing␈αfrom␈αshot.
␈β|␈↓ ↓H␈ε?M/2␈αshot␈α∩Sheri{␈αstaggering␈αto␈αtable␈αfor␈αa␈αdrink␈α.␈α⊂.␈α⊂.␈α⊂falls␈αdead.
␈β
 ␈↓ ↓H␈ε?MS␈↓ α
␈ε?Robber␈αlea␈α␈v␈α␈es␈αshack␈αwith␈αmoney␈αbags.*
␈β
[␈↓ α␈ε#[␈ε0Note:␈ε#␈α∪CU␈α∂=␈α∂\clo␈α␈se␈α∂up␈α␈",␈α⊂MS␈α∞=␈α∂\med␈α␈ium␈α∂shot"␈α␈,␈α⊂etc.␈α≠Th␈α␈e␈α∂ab␈α␈o␈α␈v␈α␈e␈α∞deta␈α␈i␈α↓ls␈α∂w␈α␈ere
␈β∞β␈↓ ↓H␈ε#k␈α␈ind␈α␈l␈α↓y␈αfurn␈α␈i␈α↓sh␈α␈ed␈αto␈α
the␈αauthor␈α
b␈α␈y␈α
Thoma␈α␈s␈α
H.␈↓ ε{␈ε#W␈α⎇olf,␈α∞pro␈α␈du␈α␈cer␈α
o␈α␈f␈α∞th␈α␈e␈α
telev␈α␈i␈α↓sio␈α␈n␈α
sho␈α␈w,
␈β∞*␈↓ ↓H␈ε#who␈α
sugg␈α␈ested␈α
th␈α␈e␈α∞ide␈α␈a␈α∞of␈α
a␈α∞c␈α␈omp␈α␈uter-written␈α
p␈α␈l␈α↓a␈α}ylet␈α∞in␈α
the␈α
|rs␈α␈t␈α∞plac␈α␈e,␈α∂a␈α␈nd␈α
also␈α
by
␈β∞R␈↓ ↓H␈ε#Do␈α␈ug␈α␈l␈α↓a␈α␈s␈αT.␈↓ αr␈ε#Ro␈α␈ss␈αand␈α
Harrison␈α
R.␈↓ ¬7␈ε#Morse␈αwho␈αp␈α␈rod␈α␈uce␈α␈d␈αth␈α␈e␈αcomp␈α␈ute␈α␈r␈αpro␈α␈gram␈α␈.␈α↓]
␈β∞z␈↓ α␈ε#The␈α	rea␈α␈der␈α	wil␈α↓l␈α	un␈α␈do␈α␈ub␈α␈tedly␈α	ha␈α}v␈α␈e␈α	man␈α}y␈α	i␈α↓d␈α␈ea␈α␈s␈α
ab␈α␈ou␈α␈t␈α
ho␈α␈w␈α	he␈α	cou␈α␈ld␈α	prep␈α␈are␈α	h␈α␈i␈α↓s␈α	o␈α␈wn
␈β∂!␈↓ ↓H␈ε#c␈α␈omp␈α␈uter␈αp␈α␈rog␈α␈ram␈αto␈αd␈α␈o␈αcre␈α␈ativ␈α␈e␈αwriting␈α␈;␈αa␈α␈nd␈α
that␈αis␈αth␈α␈e␈αpo␈α␈i␈α↓n␈α}t␈αof␈αthis␈αex␈α␈ercise.
␈β∂S␈↓ ↓;␈ε↓x
␈β∂U␈↓ ↓c␈ε36.␈↓ α␈ε#[␈ε)40␈↓ α;␈ε#]␈α⊗Lo␈α↓o␈α␈k␈αλa␈α␈t␈αλthe␈απsub␈α␈rou␈α␈ti␈α↓n␈α␈e␈αλlibra␈α␈ry␈αλof␈αλe␈α␈ach␈απcom␈α␈pu␈α␈ter␈αλinsta␈α␈l␈α↓latio␈α␈n␈αλin␈αλy␈α}ou␈α␈r␈αλorg␈α␈aniza␈α␈-
␈β∂|␈↓ ↓H␈ε#tio␈α␈n,␈αan␈α␈d␈α
replac␈α␈e␈αth␈α␈e␈αra␈α␈nd␈α␈om␈α
n␈α␈um␈α}ber␈α
gen␈α␈erato␈α␈rs␈αb␈α␈y␈αg␈α␈o␈α↓od␈α
o␈α␈nes.␈α∂T␈α⎇ry␈α
to␈α
a␈α␈v␈α␈o␈α␈i␈α↓d␈α
b␈α␈eing␈α
to␈α↓o
␈β⊂$␈↓ ↓H␈ε#shoc␈α␈k␈α␈ed␈α
at␈αwha␈α␈t␈αy␈α␈ou␈α
|n␈α␈d.
␈β⊂S␈↓ ↓H␈∧⊂S↓Hα↓X
␈β⊂[␈↓ ↓H␈ε$*␈ε8⎇␈ε$␈α1␈α↓962␈αby␈αColumbi␈α␈a␈αBro␈α↓adcasti␈α␈ng␈αSystem,␈αInc.␈α⊃All␈αRi␈α␈g␈α↓h␈α␈ts␈αRese␈α␈rv␈α␈ed.␈α∩Use␈α␈d␈αby␈αpe␈α␈rm␈α↓i␈α␈ssion.
␈β⊂|␈↓ ↓H␈ε$F␈α⎇o␈α↓r␈αλf␈α↓ur␈α␈ther␈αλinform␈α↓ation,␈αλsee␈αλJ.␈αλE␈α↓.␈↓ ¬π␈ε$Pf␈α↓e␈α␈i{e␈α␈r,␈ε1␈α	The␈αλThinki␈α␈ng␈α	Ma␈α↓c␈α␈hine␈ε$␈αλ(Ne␈α␈w␈α	Y␈α}ork:␈α	J.␈αλB␈α↓.␈αλLippi␈α␈ncott,
␈β⊃≤␈↓ ↓H␈ε$196␈α↓2).
␈β∪(

␈β↓U␈↓ ↓H␈ε"3.6␈↓ 
v␈ε"177
␈β↓\␈↓ 	∪␈ε∞S␈α␈U␈α↓MMAR␈α}Y
␈βα#␈↓ ↓;␈ε↓x
␈βα%␈↓ ↓c␈ε37.␈↓ α␈ε#[␈ε)M4␈α␈0␈↓ α\␈ε#]␈α⊗A␈αp␈α␈rogr␈α␈amme␈α␈r␈αd␈α␈ecide␈α␈d␈αto␈αencip␈α␈her␈αhis␈α|les␈αby␈αu␈α␈sing␈αa␈αli␈α↓n␈α␈ear␈αco␈α␈ngr␈α␈uen␈α}ti␈α↓a␈α␈l
␈βαG␈↓ ∧A␈ε&32␈↓ λq␈ε&32
␈βαM␈↓ ↓H␈ε#se␈α␈que␈α␈nce␈ε7␈αh␈↓ α]␈ε)X␈↓ β
␈ε7i␈ε#␈α
o␈α␈f␈α
p␈α␈eriod␈↓ ∧1␈ε#2␈↓ ∧k␈ε#g␈α␈en␈α␈erated␈αby␈α(␈ε)a␈ε#,␈ε)␈α¬c␈ε#␈α↓,␈↓ ε⎇␈ε)X␈↓ π'␈ε#)␈α
with␈ε)␈αm␈ε#␈α
=␈↓ λa␈ε#2␈↓ 	∞␈ε#.␈α∪He␈αtook␈αth␈α␈e␈αm␈α↓os␈α␈t
␈βαX␈↓ αx␈ε,n␈↓ π_␈ε&0
␈βαo␈↓ ∧β␈ε&16
␈βαt␈↓ ↓H␈ε#sig␈α␈ni|ca␈α␈n␈α␈t␈αbits␈ε7␈αb␈↓ β4␈ε)X␈↓ βb␈ε#/␈↓ βr␈ε#2␈↓ ∧ ␈ε7c␈ε#␈αan␈α␈d␈↓ ∧y␈ε#ex␈α␈clusiv␈α␈e-o␈α␈r'␈α↓e␈α␈d␈αthe␈α␈m␈αon␈α␈to␈αh␈α␈is␈αd␈α␈ata␈α␈,␈αb␈α␈ut␈αk␈α␈ep␈α␈t␈αthe␈αp␈α␈aram␈α␈-
␈ββ␈↓ βO␈ε,n
␈ββ≤␈↓ ↓H␈ε#e␈α␈ters␈ε)␈αa␈ε#,␈ε)␈αc␈ε#␈α↓,␈αan␈α␈d␈↓ β!␈ε)X␈↓ βW␈ε#se␈α␈cret.
␈ββ(␈↓ β<␈ε&0
␈ββD␈↓ α␈ε#Sho␈α␈w␈α
tha␈α␈t␈αth␈α␈i␈α↓s␈α
isn't␈αa␈α
v␈α␈e␈α␈ry␈αs␈α␈ecure␈α
sch␈α␈eme,␈α
by␈α
de␈α␈vising␈α
a␈α
method␈α
tha␈α␈t␈αd␈α␈edu␈α␈ces␈↓ 
}␈ε#the
␈ββk␈↓ ↓H␈ε#m␈α}ultiplier␈ε)␈α∞a␈ε#␈α
an␈α␈d␈α
the␈α
|rst␈α
di{e␈α␈renc␈α␈e␈↓ ¬←␈ε)X␈↓ ε∪␈ε7␈␈↓ ε=␈ε)X␈↓ εu␈ε#i␈α↓n␈α
a␈α
rea␈α␈sona␈α␈ble␈α
am␈α↓o␈α␈un␈α}t␈α∞of␈α
ti␈α↓m␈α␈e,␈α∂g␈α␈iv␈α␈en
␈ββw␈↓ ¬z␈ε&1␈↓ εY␈ε&0
␈β∧
␈↓ ∧0␈ε&16
␈β∧∪␈↓ ↓H␈ε#o␈α␈nly␈αth␈α␈e␈αv␈α}a␈α␈l␈α↓u␈α␈es␈αof␈ε7␈αb␈↓ βa␈ε)X␈↓ ∧∂␈ε#/␈↓ ∧∨␈ε#2␈↓ ∧M␈ε7c␈ε#␈αfor␈α0␈ε7␈α	∀␈ε)␈α	n␈ε#␈α
<␈α	150␈α␈.
␈β∧≡␈↓ β|␈ε,n
␈β∪(/FONT#1=cmathx[XGP,SYS]=↓xx/FONT#14=cmsc9[XGP,SYS]=ABDEMNORSUYY/FONT#21=cmtt9[XGP,SYS]=ADIJMNPRXX/FONT#32=cmsss8[XGP,SYS]=Sagg/FONT#34=cmr10[XGP,SYS]="$'()+,-./0123456789:;<=?ABCDEFGHIJLMNOPRSTUW\↑abcdefghijklmnopqrstuvwxyz{|⎇}}/FONT#35=cmr9[XGP,SYS]="$'(),-./0123456789:;<=?ABCDEFHIJLMNOPRSTUWX[\]abcdefghijklmnopqrstuvwxyz{|⎇␈␈/FONT#36=cmr8[XGP,SYS]=()*,.01269:ABCEFIJLNPRSUYabcdefghiklmnoprstuvwy{{/FONT#37=cmr7[XGP,SYS]=02399/FONT#38=cmr6[XGP,SYS]=012366/FONT#40=cmi10[XGP,SYS]=Xacdjkmptt/FONT#41=cmi9[XGP,SYS]=0123456MXYackmnn/FONT#43=cmi7[XGP,SYS]=pp/FONT#44=cmi6[XGP,SYS]=nn/FONT#45=cmi5[XGP,SYS]=tt/FONT#46=cmsc10[XGP,SYS]=ACDEHORVV/FONT#47=cms10[XGP,SYS]=.CIMRSabcdeghilmnoprstuvwxyy/FONT#48=cms9[XGP,SYS]=.:ACNSabcdeghiklmnoprtuvwyy/FONT#49=cms8[XGP,SYS]=MTaceghiknn/FONT#50=cmb10[XGP,SYS]=013466/FONT#51=cmb9[XGP,SYS]=.12345677/FONT#53=cmtt[XGP,SYS]="()*+,-.0123459=ABCDEFGHIJKLMNOPQRSTUVWXYY/FONT#54=cmsy10[XGP,SYS]=∀∃→ p⎇⎇/FONT#55=cmsy9[XGP,SYS]=∀ bchii/FONT#56=cmsy8[XGP,SYS]=q⎇⎇/FONT#61=cmssb[XGP,SYS]=.36ACEIMRSUXYY/FONT#63=cmss8[XGP,SYS]=$'()*,./12:;ABCDEFGHIKLMNOPRSTUW←abcdefghiklmnoprstuvwy{||